package com.example.algorithm.kmp;

import java.util.Arrays;

/**
 * 「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
 *  给你一个字符串 s，请你返回它的 最长快乐前缀。
 *  如果不存在满足题意的前缀，则返回一个空字符串。
 *
 *  示例 1：
 *  输入：s = "level"
 * 输出："l"
 * 解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel",
 * "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。
 *
 *  示例 2：
 *  输入：s = "ababab"
 * 输出："abab"
 * 解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。
 *
 *  示例 3：
 *  输入：s = "leetcodeleet"
 * 输出："leet"
 *
 *  示例 4：
 *  输入：s = "a"
 * 输出：""
 *
 * s 只含有小写英文字母
 */
public class Leetcode1392_LongestPrefix {
    public static void main(String[] args) {
        String s = "ababab";
        System.out.println(new Solution().longestPrefix(s));
    }

    static class Solution {
        /**
         * KMP算法
         * 在 KMP 算法中的匹配数组 next 数组，其中 next[i] 表示关于字符串 s 的子串 s[0..i] 最长的既是前缀也是后缀的字符串
         * 所以只需要返回s[0..next[s.length−1]+1 ]
         *
         * @param s
         * @return
         */
        private String longestPrefix3(String s) {
            int len = s.length();
            int[] next = new int[len];
            Arrays.fill(next, -1);
            for (int i = 1; i < len; ++i) {
                int j = next[i - 1];
                while (j != -1 && s.charAt(j + 1) != s.charAt(i)) {
                    j = next[j];
                }
                if (s.charAt(j + 1) == s.charAt(i)) {
                    next[i] = j + 1;
                }
            }
            return s.substring(0, next[len - 1] + 1);
        }

        /**
         * 解法二:字符串编码(哈希算法)
         * 选择一个大于等于 能组成字符串的所有字符种类 的数(base)
         * 将字符串用base进行编码，规则如下:
         *    code = sum(s(i) * base^(s.length - i - 1))
         * 我们从小到大枚举前缀的长度。对于枚举的长度 i，我们计算字符串 s 长度为 i 的前缀和后缀在 base=29,mod=10^9+7(常用) 时的编码值。
         * 如果这两个编码值相等，我们就可以判定该前缀和后缀相等。
         *
         * 前缀:每在字符串最后多出一个新的字符，就相当于原编码值乘以 base 再加上新的字符的编码值；
         * 后缀:每在字符串最前多出一个新的字符，就相当于原编码值加上新的字符的编码值乘以 base 的 i−1 次幂。
         *
         * @param s
         * @return
         */
        private String longestPrefix2(String s) {
            int len = s.length();
            long prefix = 0, suffix = 0;
            int max = 0;
            long base = 29, mod = 1000000007, mul = 1;// 取模是因为可能溢出
            for (int i = 1; i < len; i++) {
                prefix = (prefix * base + s.charAt(i - 1) - 'a') % mod;
                suffix = (suffix + (s.charAt(len - i) - 'a') * mul) % mod;
                if (prefix == suffix) max = i;
                mul = (mul * base) % mod;
            }
            return s.substring(0, max);
        }

        /**
         * 暴力法：逐个前后缀进行对比
         * @param s
         * @return
         */
        private String longestPrefix1(String s) {
            int len = s.length();
            for (int i = len - 1; i > 0; i--) {
                String prefix = s.substring(0, i);
                String suffix = s.substring(len - i, len);
                if (prefix.equals(suffix)) return prefix;
            }
            return "";
        }

        public String longestPrefix(String s) {
            return longestPrefix3(s);
        }
    }
}
